import java.util.Comparator;
import java.util.LinkedList;

public class ShellSort<T> {

    private Comparator<T> comparator;

    public ShellSort(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    public void sort(T[] array) {
        LinkedList<Integer> stepSequence = shellStepSequence(array.length);

        for (Integer step : stepSequence) {
            sortByStep(array, step);
        }
    }

    private void sortByStep(T[] array, int step) {
        for (int col = 0; col < step; col++) {
            for (int i = col + step; i < array.length; i += step) {
                for (int j = i; j > col && comparator.compare(array[j - 1], array[j]) > 0; j -= step) {
                    swap(array, j - 1, j);
                }
            }
        }
    }

    private LinkedList<Integer> shellStepSequence(int n) {
        LinkedList<Integer> stepSequence = new LinkedList<>();

        while ((n >>= 1) > 0) {
            stepSequence.add(n);
        }

        return stepSequence;
    }

    private void swap(T[] array, int i, int j) {
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
